package zuo.algo.c07;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

/**
 * 01:08-判断一颗树是否是满二叉树
 * 树的节点个数 = 2**树的高度 - 1
 */
public class TestFull {

    public static boolean isFull(TreeNode head) {
        if (head == null) {
            return true;
        }
        Info info = full(head);
        return info.nodes == (Math.pow(2, info.height) - 1);
    }

    public static Info full(TreeNode node) {
        if (node == null) {
            return new Info(0, 0);
        }
        Info left = full(node.left);
        Info right = full(node.right);
        int height = Math.max(left.height, right.height) + 1;
        int nodes = left.nodes + right.nodes + 1;
        return new Info(height, nodes);
    }

    public static class Info {
        public int height;
        public int nodes;

        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static void main(String[] args) {
        TreeNode head = TreeUtils.getTree();
        boolean full = isFull(head);
        System.out.println(full);
        head.right.right.right = null;
        full = isFull(head);
        System.out.println(full);
    }
}
